import bisect
from collections import deque
from typing import *


class Solution:
    def leftmostBuildingQueries(
        self, heights: List[int], queries: List[List[int]]
    ) -> List[int]:
        # heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
        for i, (a, b) in enumerate(queries):  # case2还是有良心的..这个右端未必是大的
            if a > b:
                queries[i][0], queries[i][1] = b, a
        ans = [-1] * len(queries)  # 答案
        idx = [i for i in range(len(queries))]  # queries问询的位置
        idx.sort(
            key=lambda a: queries[a][1], reverse=True
        )  # 按照queries右端从大到小处理
        q = deque()  # 单调队列，每个查询位置右侧高度单调升序
        i = len(heights) - 1
        for id in idx:
            l, r = queries[id][0], queries[id][1]
            while i >= r:  # 右端单调升序
                while len(q) > 0 and heights[i] >= heights[q[0]]:  # 小于等于的弹出
                    q.popleft()
                q.appendleft(i)  # 添加到左端
                i -= 1
            if r == l:  # 已经在同一个位置上了
                ans[id] = l
            elif heights[r] > heights[l]:  # 左界跳到右界上
                ans[id] = r
            else:  # 左界右界一起往右跳
                j = bisect.bisect_right(  # heights[i] < heights[j] 找第一个大于两者最大的地方
                    q,
                    max(heights[l], heights[r]),
                    key=lambda a: heights[a],  # 二分检索
                )
                ans[id] = (
                    q[j] if j < len(q) else -1
                )  # 越界说明没有返回-1，否则返回heights索引
        return ans


s = Solution()
print(
    s.leftmostBuildingQueries(
        heights=[6, 4, 8, 5, 2, 7], queries=[[0, 1], [0, 3], [2, 4], [3, 4], [2, 2]]
    )
)
print(
    s.leftmostBuildingQueries(
        heights=[5, 3, 8, 2, 6, 1, 4, 6],
        queries=[[0, 7], [3, 5], [5, 2], [3, 0], [1, 6]],
    )
)
